home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 22 / Cream of the Crop 22.iso / program / cgazv3n4.zip / ROOT-DIR.ZIP / BM.C next >
C/C++ Source or Header  |  1989-05-31  |  6KB  |  221 lines
  1. /***************************************************************
  2.  *
  3.  * Boyer-Moore string search routine
  4.  *
  5.  * Author:    John Rex
  6.  * References: (1) Boyer RS, Moore JS: "A fast string searching
  7.  *                 algorithm"  CACM 20(10):762-777, 1977
  8.  *             (2) plus others--see text of article
  9.  *
  10.  * Compilers: Microsoft C V5.1  - compile as is
  11.  *            Turbo C V2.0      - compile as is
  12.  *
  13.  * Compile time preprocessor switches:
  14.  *    DEBUG - if defined, include test driver
  15.  *
  16.  * Usage:
  17.  *
  18.  *   char *pattern, *text;  - search for pattern in text
  19.  *   unsigned length;       - length of text (the routine does
  20.  *                            NOT stop for '\0' bytes, thus
  21.  *                            allowing it to search strings
  22.  *                            stored sequentially in memory.
  23.  *   char *start;           - pointer to match
  24.  *
  25.  *   char *Boyer_Moore(char *, char *, unsigned);
  26.  *
  27.  *   start = Boyer_Moore(pattern, text, strlen(text);
  28.  *
  29.  *   NULL is returned if the search fails.
  30.  *
  31.  *   Switches: if defined:
  32.  *
  33.  *      DEBUG will cause the search routine to dump its tables
  34.  *            at various times--this is useful when trying to
  35.  *            understand how upMatchJump is generated
  36.  *
  37.  *      DRIVER will cause a test drive to be compiled
  38.  *
  39.  * Source code may be used freely if source is acknowledged.
  40.  * Object code may be used freely.
  41.  **************************************************************/
  42.  
  43. #define DRIVER
  44.  
  45. #if defined(DEBUG)
  46. #define SHOWCHAR for (uT=1; uT<=uPatLen; uT++)  \
  47.                  printf(" %c ", pcPattern[uT-1])
  48. #define SHOWJUMP for (uT=1;uT<=uPatLen;uT++)    \
  49.                  printf("%2d ", upMatchJump[uT])
  50. #define SHOWA    printf("  uA = %u  ", uA)
  51. #define SHOWB    printf("  uB = %u", uB)
  52. #define SHOWBACK for (uT=1;uT<=uPatLen;uT++)    \
  53.                  printf("%2d ", upBackUp[uT])
  54. #define NL       printf("\n")
  55.  
  56. unsigned uT;
  57. #else
  58. #define SHOWCHAR
  59. #define SHOWJUMP
  60. #define SHOWA
  61. #define SHOWB
  62. #define SHOWBACK
  63. #define NL
  64. #endif
  65.  
  66. #include <stdio.h>
  67. #include <stdlib.h>
  68. #include <string.h>
  69.  
  70. #define AlphabetSize 256
  71.  
  72. char *Boyer_Moore(pcPattern, pcText, uTextLen)
  73. char *pcPattern;        /* we search for this ... */
  74. char *pcText;           /* ... in this text ...   */
  75. unsigned uTextLen;      /* ... up to this length  */
  76. {
  77.              /* array of character mis-match offsets */
  78.     unsigned uCharJump[AlphabetSize];
  79.              /* array of offsets for partial matches */
  80.     unsigned *upMatchJump;
  81.              /* temporary array for upMatchJump calc */
  82.     unsigned *upBackUp;
  83.     unsigned u, uPatLen;
  84.     unsigned uText, uPat, uA, uB;
  85.  
  86.  
  87.     /* Setup and initialize arrays */
  88.     uPatLen = strlen(pcPattern);
  89.     upMatchJump = (unsigned *)
  90.          malloc(2 * (sizeof(unsigned) * (uPatLen + 1)) );
  91.     upBackUp = upMatchJump + uPatLen + 1;
  92.  
  93.     /* Heuristic #1 -- simple char mis-match jumps ... */
  94.     memset(uCharJump, 0, AlphabetSize*sizeof(unsigned));
  95.     for (u = 0 ; u < uPatLen; u++)
  96.         uCharJump[((unsigned char) pcPattern[u])]
  97.                      = uPatLen - u - 1;
  98.  
  99.     /* Heuristic #2 -- offsets from partial matches ... */
  100.     for (u = 1; u <= uPatLen; u++)
  101.         upMatchJump[u] = 2 * uPatLen - u;
  102.                                 /* largest possible jump */
  103.     SHOWCHAR; NL;
  104.     SHOWJUMP; NL;
  105.  
  106.     u = uPatLen;
  107.     uA = uPatLen + 1;
  108.     while (u > 0) {
  109.         upBackUp[u] = uA;
  110.         while( uA <= uPatLen &&
  111.           pcPattern[u - 1] != pcPattern[uA - 1]) {
  112.             if (upMatchJump[uA] > uPatLen - u)
  113.                 upMatchJump[uA] = uPatLen - u;
  114.             uA = upBackUp[uA];
  115.         }
  116.         u--;
  117.         uA--;
  118.     }
  119.  
  120.     SHOWJUMP; SHOWA; SHOWBACK; NL;
  121.  
  122.     for (u = 1; u <= uA; u++)
  123.         if (upMatchJump[u] > uPatLen + uA - u)
  124.             upMatchJump[u] = uPatLen + uA - u;
  125.  
  126.     uB = upBackUp[uA];
  127.     SHOWJUMP; SHOWB; NL;
  128.  
  129.     while (uA <= uPatLen) {
  130.         while (uA <= uB) {
  131.             if (upMatchJump[uA] > uB - uA + uPatLen)
  132.                 upMatchJump[uA] = uB - uA + uPatLen;
  133.             uA++;
  134.         }
  135.         uB = upBackUp[uB];
  136.     }
  137.     SHOWJUMP; NL;
  138.  
  139.     /* now search */
  140.     uPat = uPatLen;         /* tracks position in Pattern */
  141.     uText = uPatLen - 1;    /* tracks position in Text */
  142.     while (uText < uTextLen && uPat != 0) {
  143.         if (pcText[uText] == pcPattern[uPat - 1]) { /* match? */
  144.             uText--;    /* back up to next */
  145.             uPat--;
  146.         }
  147.         else { /* a mismatch - slide pattern forward */
  148.             uA = uCharJump[((unsigned char) pcText[uText])];
  149.             uB = upMatchJump[uPat];
  150.             uText += max(uA, uB);  /* select larger jump */
  151.             uPat = uPatLen;
  152.         }
  153.     }
  154.  
  155.     /* return our findings */
  156.     if (uPat == 0)
  157.         return(pcText + (uText + 1)); /* have a match */
  158.     else
  159.         return (NULL); /* no match */
  160. }
  161.  
  162. #pragma subtitle("Test Driver")
  163.  
  164. #ifdef DRIVER
  165.  
  166. #define PATTERN argv[1]
  167. #define TEXT_SIZE 32000u
  168.  
  169. void main(argc, argv)
  170. int argc;
  171. char **argv;
  172. {
  173.     char *start, *p;
  174.     char text[TEXT_SIZE];
  175.     int i;
  176.     unsigned length, count;
  177.     FILE *infile;
  178.  
  179.     if (argc != 3) {
  180.         puts("Usage is: bm pattern file\n");
  181.         exit(0);
  182.     }
  183.  
  184.     if ((infile = fopen(argv[2], "r")) == NULL) {
  185.         puts("Can't open input file\n");
  186.         exit(0);
  187.     }
  188.  
  189.     /* read in whole file */
  190.     length = fread(text, 1, TEXT_SIZE, infile);
  191.     fclose(infile);
  192.     p=text;
  193.     count=0;
  194.     while (count < length) {
  195.         if (*p == '\n')
  196.             *p = '\0';
  197.         p++;
  198.         count++;
  199.     }
  200.  
  201.     /* now search repeatedly */
  202.     start = Boyer_Moore(PATTERN, text, length);
  203.     while (start != NULL) {
  204.         for (p = start; ; p--) { /* find start of line */
  205.             if (*p == '\0') {
  206.                 p++;
  207.                 break;
  208.             }
  209.             else if (p == text)
  210.                 break;
  211.         }
  212.         printf("Match:\n%s\n", p);
  213.         for (i=start-p; i>0; i--)
  214.             fputc(' ', stdout);
  215.         printf("%s\n\n", PATTERN);
  216.         start = Boyer_Moore(PATTERN, start+1,
  217.                              length - (start-text) - 1);
  218.     }
  219. }
  220. #endif
  221.